package com.company;

import java.util.ArrayList;
import java.util.HashSet;

public class Solution547 {
    public void dfs(int[][] isConnected,boolean[] visit, int tmp){
        visit[tmp]=true;
        for (int i = 0; i < isConnected[0].length; i++) {
            if (isConnected[tmp][i]==1&&visit[i]==false){
                dfs(isConnected,visit,i);
            }
        }
    }
    public int findCircleNum(int[][] isConnected) {
        int result=0;
        boolean[] visit=new boolean[isConnected.length];
        for (int i = 0; i < isConnected.length; i++) {
            visit[i]=false;
        }
        for (int i = 0; i < visit.length; i++) {
            if(visit[i]==false){
                dfs(isConnected,visit,i);
                result++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution547 s=new Solution547();
        System.out.println(s.findCircleNum(new int[][]{
                {1,1,0,0,0,0,0,1,0,0,0,0,0,0,0},
                {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,1,0,1,1,0,0,0,0,0,0,0,0},
                {0,0,0,0,1,0,0,0,0,1,1,0,0,0,0},
                {0,0,0,1,0,1,0,0,0,0,1,0,0,0,0},
                {0,0,0,1,0,0,1,0,1,0,0,0,0,1,0},
                {1,0,0,0,0,0,0,1,1,0,0,0,0,0,0},
                {0,0,0,0,0,0,1,1,1,0,0,0,0,1,0},
                {0,0,0,0,1,0,0,0,0,1,0,1,0,0,1},
                {0,0,0,0,1,1,0,0,0,0,1,1,0,0,0},
                {0,0,0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,0,1,0,1,0,0,0,0,1,0},
                {0,0,0,0,0,0,0,0,0,1,0,0,0,0,1}}));
    }
}
